\documentclass{article}

\usepackage{gastex}
\usepackage[usenames]{color}
\usepackage[T1]{fontenc}

\renewcommand{\labelenumi}{\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii})}

\begin{document}

Aufgabe 3.2.3:\\
\\
Die Übergangstabelle eines DEA siehe wie folgt aus:\\

\begin{tabular}{c|l|l|}
                   		   & 0       & 1        \\
\hline \hline

$\rightarrow p^{\ast}$   & $s    $ & $p    $  \\
\hline
$q$    				 		       & $p    $ & $s    $  \\
\hline
$r$        							 & $r    $ & $q    $	\\
\hline
$s$											 & $q$     & $r$			\\
\hline
\end{tabular}
%--------------------------------------------
\\
\\
Die Graph eines DEA sehe wie folgt aus:
 	


  \begin{center}
  	
    \unitlength=4pt
    \begin{picture}(30, 36)(0,-18)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=1}
    \thinlines
    \node[Nmarks=ir,iangle=180](p)(0,0){$p$}
    \node(s)(15,10){$s$}
    \node(q)(15,-10){$q$}
    \node(r)(30,0){$r$}
    \drawloop[loopangle=180](p){$1$}
    \drawloop[loopangle=0](r){$0$}
    %\drawloop[loopangle=270](q){$b$}
    %\drawloop[loopangle=90](r){$c$}
    \drawedge(p,s){$0$}
    \drawedge[ELside=l](q,p){$0$}
    \drawedge(q,s){$1$}
    \drawedge(s,q){$0$}
    \drawedge(s,r){$1$}
    \drawedge(r,q){$1$}
    \end{picture}
  \end{center}
  
Als erstes werden die Zeichenketten an den Pfeilen des Graphen als Ausdrücke geschrieben, in dem sie \textbf{fett} geschrieben werden. Diesen Schritt sparen wir uns, da es nichts am Aussehen und der Struktur des Graphen ändert. Statt dessen werden wir gleich dazu übergehen den ersten Zustand des Graphen zu eliminieren. Dieser ist im Grunde frei wählbar. Am Schluss muss der Graph bis auf 2 Zustände reduziert sein, den Start- und den Endzustand. Da diese beiden in diesem Fall $p$ sind, wird der minimierte Automat am Ende nur noch aus einem Zustand, nämlich $p$ bestehen.\\
Als erstes werden wir Zustand $q$ eliminieren. Dazu muss jeder Pfad der über $q$ führt zu einem neuen Pfad gemacht werden, der ohne den Zustand $q$ auskommt.Welche Pfade müssen hier also erzeugt werden:
\begin{enumerate}
	\item
	Ein Pfad führt von $r$ über $q$ nach $s$.
	\item
	Ein Pfad führt von $r$ über $q$ nach $p$.
	\item
	Ein Pfad führt von $s$ über $q$ nach $p$.
	\item
	Ein Pfad führt von $s$ über $q$ zurück nach $s$.
\end{enumerate}
Wir müssen also für jeden der Möglichen Pfade über q (a, b, c, und d) einen Ausdruck formulieren, der die Zeichenreihe beschreibt, welche auf genau diesen Pfaden steht.

\begin{enumerate}
	\item
	Der Pfad von $r$ über $q$ nach $s$ wird beschriftet mit \textbf{$11$}.\\
	Von $r$ aus kommt eine 1 (was zu Zustand $q$ führt), gefolgt von einer 1 (was den Zustand des Automaten dann von $q$ auf $s$ ändert, womit wir den gesuchten Pfad abgedeckt hätten.\\
	Dies führt zu folgendem Automaten:
	\begin{center}
    \unitlength=4pt
    \begin{picture}(30, 36)(0,-18)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=1}
    \thinlines
    \node[Nmarks=ir,iangle=180](p)(0,0){$p$}
    \node(s)(15,10){$s$}
    \node(q)(15,-10){$q$}
    \node(r)(30,0){$r$}
    \drawloop[loopangle=0](r){$\textbf{0}$}
    \drawloop[loopangle=180](p){$1$}
    %\drawloop[loopangle=270](q){$b$}
    %\drawloop[loopangle=90](r){$c$}
    \drawedge(p,s){$\textbf{0}$}
    \drawedge[ELside=l](q,p){$\textbf{0}$}
    \drawedge(q,s){$\textbf{1}$}
    \drawedge(s,q){$\textbf{0}$}
    \drawedge(s,r){$\textbf{1}$}
    \drawedge(r,q){$\textbf{1}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    \drawedge[ELside=r](r,s){\textbf{$11$}}
    \end{picture}
  \end{center}
  \emph{Die "`ersetzten"' Pfade werden hier noch nicht entfernt, da sonst bei weiteren Schritten leicht Fehler auftreten könnten.}
	\item
	Der Pfad von $r$ über $q$ nach $p$ wird beschriftet mit \textbf{$11$}.\\
	Erklärung analog zu oben.\\
	Dies führt zu folgendem Automaten:
	\begin{center}
    \unitlength=4pt
    \begin{picture}(30, 36)(0,-18)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=1}
    \thinlines
    \node[Nmarks=ir,iangle=180](p)(0,0){$p$}
    \node(s)(15,10){$s$}
    \node(q)(15,-10){$q$}
    \node(r)(30,0){$r$}
    \drawloop[loopangle=0](r){$\textbf{0}$}
    \drawloop[loopangle=180](p){$1$}
    %\drawloop[loopangle=270](q){$b$}
    %\drawloop[loopangle=90](r){$c$}
    \drawedge(p,s){$\textbf{0}$}
    \drawedge[ELside=l](q,p){$\textbf{0}$}
    \drawedge(q,s){$\textbf{1}$}
    \drawedge(s,q){$\textbf{0}$}
    \drawedge(s,r){$\textbf{1}$}
    \drawedge(r,q){$\textbf{1}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    \drawedge[ELside=r](r,s){\textbf{$11$}}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=15}
    \drawedge(r,p){\textbf{10}}
    \end{picture}
  \end{center}
  \newpage
  \item
  Der Pfad von $s$ über $q$ nach $p$ wird beschriftet mit \textbf{$00$}
	\begin{center}
    \unitlength=4pt
    \begin{picture}(30, 36)(0,-18)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=1}
    \thinlines
    \node[Nmarks=ir,iangle=180](p)(0,0){$p$}
    \node(s)(15,10){$s$}
    \node(q)(15,-10){$q$}
    \node(r)(30,0){$r$}
    \drawloop[loopangle=0](r){$\textbf{0}$}
    \drawloop[loopangle=180](p){$1$}
    %\drawloop[loopangle=270](q){$b$}
    %\drawloop[loopangle=90](r){$c$}
    \drawedge(p,s){$\textbf{0}$}
    \drawedge[ELside=l](q,p){$\textbf{0}$}
    \drawedge(q,s){$\textbf{1}$}
    \drawedge(s,q){$\textbf{0}$}
    \drawedge(s,r){$\textbf{1}$}
    \drawedge(r,q){$\textbf{1}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    \drawedge[ELside=r](r,s){\textbf{$11$}}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=15}
    \drawedge(r,p){\textbf{10}}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    \drawedge[ELside=r](s,p){\textbf{00}}
    \end{picture}
  \end{center}
  \item
  Der Pfad von $s$ über $q$ zuück zu $s$ wird beschriftet mit \textbf{$01$}.
  \begin{center}
    \unitlength=4pt
    \begin{picture}(30, 36)(0,-18)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=1}
    \thinlines
    \node[Nmarks=ir,iangle=180](p)(0,0){$p$}
    \node(s)(15,10){$s$}
    \node(q)(15,-10){$q$}
    \node(r)(30,0){$r$}
    \drawloop[loopangle=0](r){$\textbf{0}$}
    \drawloop[loopangle=180](p){$1$}
    %\drawloop[loopangle=270](q){$b$}
    %\drawloop[loopangle=90](r){$c$}
    \drawedge(p,s){$\textbf{0}$}
    \drawedge[ELside=l](q,p){$\textbf{0}$}
    \drawedge(q,s){$\textbf{1}$}
    \drawedge(s,q){$\textbf{0}$}
    \drawedge(s,r){$\textbf{1}$}
    \drawedge(r,q){$\textbf{1}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    \drawedge[ELside=r](r,s){$\textbf{11}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=15}
    \drawedge(r,p){\textbf{10}}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    \drawedge[ELside=r](s,p){$\textbf{00}$}
    \drawloop(s){\textbf{$\textbf{01}$}}
    \end{picture}
  \end{center}  
\end{enumerate}
  
Nun kann man alle ersetzten Pfade weglassen, was zu diesem Automaten führt:
  \begin{center}
    \unitlength=4pt
    \begin{picture}(30, 36)(0,-18)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=1}
    \thinlines
    \node[Nmarks=ir,iangle=180](p)(0,0){$p$}
    \node(s)(15,10){$s$}
    %\node(q)(15,-10){$q$}
    \node(r)(30,0){$r$}
    \drawloop[loopangle=0](r){$\textbf{0}$}
    \drawloop[loopangle=180](p){$1$}
    %\drawloop[loopangle=270](q){$b$}
    %\drawloop[loopangle=90](r){$c$}
    \drawedge(p,s){$\textbf{0}$}
    %\drawedge[ELside=l](q,p){$\textbf{0}$}
    %\drawedge(q,s){$\textbf{1}$}
    %\drawedge(s,q){$\textbf{0}$}
    \drawedge(s,r){$\textbf{1}$}
    %\drawedge(r,q){$\textbf{1}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    \drawedge[ELside=r](r,s){$\textbf{11}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=15}
    \drawedge(r,p){\textbf{10}}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    \drawedge[ELside=r](s,p){$\textbf{00}$}
    \drawloop(s){\textbf{$\textbf{01}$}}
    \end{picture}
  \end{center}
  
Im nächsten Schritt wird Zustand $r$ eliminiert. Dazu wird genau das selbe Schema wie oben angewendet.
\begin{enumerate}
	\item
	Ein Pfad führt von $s$ über $r$ zu $p$.
	\item
	Ein Pfad führt von $s$ über $r$ zurück nach $s$.
\end{enumerate}  

\begin{enumerate}
	\item
	Der Pfad von $s$ über $r$ zu $p$ wird beschriftet mit \textbf{$10^{\ast}10$}. Da es aber schon einen Pfad von $s$ nach $p$ gibt, wird der existierenden Pfad mit einer Vereinigung des alten und des neuen Ausdrucks beschriftet:
	\begin{center}
    \unitlength=4pt
    \begin{picture}(30, 36)(0,-18)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=1}
    \thinlines
    \node[Nmarks=ir,iangle=180](p)(0,0){$p$}
    \node(s)(15,10){$s$}
    \node(r)(30,0){$r$}
    \drawloop[loopangle=0](r){$\textbf{0}$}
    \drawloop[loopangle=180](p){$1$}
    \drawedge(p,s){$\textbf{0}$}
    \drawedge(s,r){$\textbf{1}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    \drawedge[ELside=r](r,s){$\textbf{11}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=15}
    \drawedge(r,p){\textbf{10}}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    \drawedge[ELside=r](s,p){$00 + 10^{\ast}10$}
    \drawloop(s){$\textbf{01}$}
    \end{picture}
  \end{center}
  \item
  Der Ausdruck auf dem schon existierenden Pfad von $s$ zu sich selbst, wird nun noch mit dem Ausdruck für den Pfad von $s$ über $r$ zurück zu $s$ ($10^{\ast}11$) vereinigt:
  \begin{center}
    \unitlength=4pt
    \begin{picture}(30, 36)(0,-18)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=1}
    \thinlines
    \node[Nmarks=ir,iangle=180](p)(0,0){$p$}
    \node(s)(15,10){$s$}
    \node(r)(30,0){$r$}
    \drawloop[loopangle=0](r){$\textbf{0}$}
    \drawloop[loopangle=180](p){$1$}
    \drawedge(p,s){$\textbf{0}$}
    \drawedge(s,r){$\textbf{1}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    \drawedge[ELside=r](r,s){$\textbf{11}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=15}
    \drawedge(r,p){\textbf{10}}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    \drawedge[ELside=r](s,p){$00 + 10^{\ast}10$}
    \drawloop(s){$\textbf{01} + 10^{\ast}11$}
    \end{picture}
  \end{center}
  \newpage
  Nun können sowohl der Zustand $r$ als auch alle Pfade zu und von $r$ weggelassen werden. Dies führt zu folgendem Automaten:
  
	\begin{center}
    \unitlength=4pt
    \begin{picture}(30, 36)(0,-18)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=1}
    \thinlines
    \node[Nmarks=ir,iangle=180](p)(0,0){$p$}
    \node(s)(15,10){$s$}
    %\node(r)(30,0){$r$}
    %\drawloop[loopangle=0](r){$\textbf{0}$}
    \drawloop[loopangle=180](p){$1$}
    \drawedge(p,s){$\textbf{0}$}
    %\drawedge(s,r){$\textbf{1}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    %\drawedge[ELside=r](r,s){$\textbf{11}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=15}
    %\drawedge(r,p){\textbf{10}}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    \drawedge[ELside=r](s,p){$00 + 10^{\ast}10$}
    \drawloop(s){$\textbf{01} + 10^{\ast}11$}
    \end{picture}
  \end{center}
\end{enumerate}

Als letztes muss nun noch der Zustand $s$ eliminiert werden, damit der Automat minimal ist. Dazu muss nur der Pfad beschrieben werden, der von $p$ über $s$ zurück zu $q$ führt. Dieser lautet $0(01 + 10^{\ast}11)^{\ast}(00 + 10^{\ast}10)$. Dies ist der Pfad von $p$ nach $p$. Dieser wird vereinigt mit dem schon existierenden Pfad, was zum finalen Automaten führt, an dem mal gleichzeitig den finalen Ausdruck ablesen kann:
\begin{center}
    \unitlength=4pt
    \begin{picture}(30, 36)(0,-18)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=1}
    \thinlines
    \node[Nmarks=ir,iangle=180](p)(0,0){$p$}
    %\node(s)(15,10){$s$}
    %\node(r)(30,0){$r$}
    %\drawloop[loopangle=0](r){$\textbf{0}$}
    \drawloop[loopangle=0](p){$1 + 0(01 + 10^{\ast}11)^{\ast}(00 + 10^{\ast}10)$}
    %\drawedge(p,s){$\textbf{0}$}
    %\drawedge(s,r){$\textbf{1}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    %\drawedge[ELside=r](r,s){$\textbf{11}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=15}
    %\drawedge(r,p){\textbf{10}}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=-5}
    %\drawedge[ELside=r](s,p){$00 + 10^{\ast}10$}
    %\drawloop(s){$\textbf{01} + 10^{\ast}11$}
    \end{picture}
  \end{center}
Damit lautet der reguläre Ausdruck, der duch Eliminierung von Zuständen erzeugt wurde:
\begin{equation}
	(1 + 0(01 + 10^{\ast}11)^{\ast}(00 + 10^{\ast}10))^{\ast}
\end{equation}
Dass vom Ausdruck die kleensche Hülle gebildet werden muss erklärt sich dadurch, dass der Automat auch schon ohne Eingabe akzepiert - beduetet: der Ausdruck der zum akzeptierenden Zustand führt, kann beliebig oft (auch 0 mal) auftreten.


\end{document}